// use std::borrow::{Borrow, BorrowMut}; // 引入
use std::rc::Rc;
use std::cell::RefCell;
use std::str::{SplitWhitespace, Split};

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}

fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut res: Vec<i32> = Vec::new();
    let mut stack = vec![];
    
    let mut root = root; // variable shadowing
    while !stack.is_empty() || root.is_some() {
        while let Some(node) = root {
            root = node.borrow().left.clone();
            stack.push(node);
        }

        if let Some(node) = stack.pop() {
            res.push(node.borrow().val);
            root = node.borrow().right.clone();
        }
    }
    res
}

fn inorder_recursive(root: &Option<Rc<RefCell<TreeNode>>>) {
    match root {
        Some(node) => {
            // let tmp = node.borrow_mut();
            inorder_recursive(&node.borrow().left);
            println!(" {}", node.borrow().val);
            inorder_recursive(&node.borrow().right);
        }
        None => {}
    }
}

// using preorder / dfs to serialize the tree
pub fn serialize(root: Option<Rc<RefCell<TreeNode>>>) -> String {
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>) -> String {
        match node {
            Some(n) => {
                format!("{} {} {}",
                    &n.borrow().val.to_string(),
                    dfs(&n.borrow().left),
                    dfs(&n.borrow().right)
                )
            }
            None => "n".to_string()
        }
    }
    dfs(&root)
}

pub fn deserialize(data: &str) -> Option<Rc<RefCell<TreeNode>>> {
    let mut elements: SplitWhitespace = data.split_whitespace();
    fn builder(elements: &mut SplitWhitespace) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(val) = elements.next() {
            if val != "n" {
                let node = Rc::new(RefCell::new(TreeNode::new(val.parse::<i32>().unwrap())));
                node.borrow_mut().left = builder(elements);
                node.borrow_mut().right = builder(elements);
                Some(node)
            } else {
                None
            }
        } else {
            None
        }
    }
    return builder(&mut elements);
}

// 331
fn is_valid_serialization(preorder: String) -> bool {
    let mut elements = preorder.split(",");
    let mut diff: i32 = 1; // diff = outdegree - indegree , 只有出度1，等待到来的节点（相当于空档的槽位）
    while let Some(n) = elements.next() {
        diff -= 1; // 来了一个节点，必定使得入度增加
        if diff < 0 {
            return false;
        }
        if n != "#" { // 非空节点带来两个新的出度
            diff += 2;
        }
    }
    return diff == 0;
}

#[test]
fn test_binary_tree() {
    // 4 -7 n n -3 -9 9 6 0 n -1 n n 6 -4 n n n n -7 -6 5 n n n -6 9 -2 n n n n -3 -4 n n n 
    let root = deserialize("1 2 4 n n 5 n n 3 6 n n 7 n n");
    inorder_recursive(&root);
    let ans = inorder_traversal(root.clone());
    println!("inorder:{:?}", ans);
    println!("{}", serialize(root));  // take ownership
    // cannot access root here
}